import 'dart:math';
import '../../utils/assorted_methods.dart';

class Coordinate {
  int row;
  int column;
  Coordinate(this.row, this.column);

  bool inbounds(List<List<int>> matrix) => row >= 0 && column >= 0 && row < matrix.length && column < matrix[0].length;
  bool isBefore(Coordinate p) => row <= p.row && column <= p.column;
  clone() => new Coordinate(row, column);


  void moveDownRight() {
    row++;
    column++;
  }

  void setToAverage(Coordinate min, Coordinate max) {
    row = (min.row + max.row) ~/ 2;
    column = (min.column + max.column) ~/ 2;
  }
}

Coordinate partitionAndSearch(List<List<int>> matrix, Coordinate origin, Coordinate dest, Coordinate pivot, int elem) {
  Coordinate lowerLeftOrigin = new Coordinate(pivot.row, origin.column);
  Coordinate lowerLeftDest = new Coordinate(dest.row, pivot.column - 1);
  Coordinate upperRightOrigin = new Coordinate(origin.row, pivot.column);
  Coordinate upperRightDest = new Coordinate(pivot.row - 1, dest.column);

  Coordinate lowerLeft = findElement(matrix, lowerLeftOrigin, lowerLeftDest, elem);
  if (lowerLeft == null) {
    return findElement(matrix, upperRightOrigin, upperRightDest, elem);
  }

  return lowerLeft;
}

Coordinate findElement(List<List<int>> matrix, Coordinate origin, Coordinate dest, int x) {

  if (!origin.inbounds(matrix) || !dest.inbounds(matrix)) {
    return null;
  }

  if (matrix[origin.row][origin.column] == x) {
    return origin;
  } else if (!origin.isBefore(dest)) {
    return null;
  }

  /**
   * Set start to start of diagonal and end to the end of the diagonal. Since
   * the grid may not be square, the end of the diagonal may not equal dest.
   */
  Coordinate start = origin.clone();
  int diagDist = min(dest.row - origin.row, dest.column - origin.column);
  Coordinate end = new Coordinate(start.row + diagDist, start.column + diagDist);
  Coordinate p = new Coordinate(0, 0);

  /* Do binary search on the diagonal, looking for the first element greater than x */
  while (start.isBefore(end)) {
    p.setToAverage(start, end);
    if (x > matrix[p.row][p.column]) {
      start.row = p.row + 1;
      start.column = p.column + 1;
    } else {
      end.row = p.row - 1;
      end.column = p.column - 1;
    }
  }

  /* Split the grid into quadrants. Search the bottom left and the top right. */
  return partitionAndSearch(matrix, origin, dest, start, x);
}

Coordinate findelementFromMatrix(List<List<int>> matrix, int x) {
  Coordinate origin = new Coordinate(0, 0);
  Coordinate dest = new Coordinate(matrix.length - 1, matrix[0].length - 1);
  return findElement(matrix, origin, dest, x);
}

void main() {
  List<List<int>> matrix = [[15, 30,  50,  70,  73],
                            [35, 40, 100, 102, 120],
                            [36, 42, 105, 110, 125],
                            [46, 51, 106, 111, 130],
                            [48, 55, 109, 140, 150]];

  printIntMatrix(matrix);
  int m = matrix.length;
  int n = matrix[0].length;

  int count = 0;
  int littleOverTheMax = matrix[m - 1][n - 1] + 10;
  for (int i = 0; i < littleOverTheMax; i++) {
    Coordinate c = findelementFromMatrix(matrix, i);
    if (c != null) {
      print("$i: (${c.row}, ${c.column})");
      count++;
    }
  }

  print("Found $count unique elements.");
}